package backtrack_or_fs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 将 n 个皇后放置在 n×n 的棋盘上  任何两个皇后都不能处于同一条横行、纵行或斜线上
 *
 *  行层用递归  列层用遍历   回溯法
 *
 */


class N皇后II_52_重做版 {
            public int totalNQueens(int n) {
                // 遍历行 每行选一个
                // 保存列  正斜线  row - i 相同 从 1-n ~ n -1   反斜线 row + i 从  0 ~ 2n -1 的列号
                int[] column = new int[n];
                int[] slash = new int[2 * n - 1];
                int[] backSlash = new int[2 * n - 1];
                return bt(0, n, column, slash, backSlash);
            }
            
            // 行号 
            private int bt(int row, int n, int[] column, int[] slash, int[] backSlash) {
                if(row == n) return 1; // 到n - 1列都能够填充数字  递归到n返回1
                int res = 0;
                for(int i = 0; i< n ; i++) {
                    if(column[i] == 1 || slash[row - i + n -1] == 1 || backSlash[i + row ] == 1) continue;
                    column[i] = 1;
                    slash[row - i + n -1] = 1;
                    backSlash[i + row ] = 1;
                    res += bt(row + 1, n, column, slash, backSlash); // 每层收集下一层中的填充方式总和
                    // 不选这一列的话 下一个for中应该把这一列的标记还原
                    column[i] = 0;
                    slash[row - i + n -1] = 0;
                    backSlash[i + row ] = 0;
                }
                return res;
            
            }
        }
public class N皇后II_52 {
    int  totalN = 0;
    Set<Integer> columnExist = new HashSet<>();
    Set<Integer> forwardSlashExist = new HashSet<>();
    Set<Integer> backSlashExist = new HashSet<>();

    public int totalNQueens(int n) {
       backtrack(0, n , columnExist, forwardSlashExist, backSlashExist);
       return totalN;
    }

    public void backtrack(int row, int n , Set<Integer> columnExist, Set<Integer> forwardSlashExist, Set<Integer> backSlashExist) {
        if(row == n) {
            totalN ++ ;
            return;
        }
        for(int i = 0; i< n ; i++) {
            // 该列存在值
            if(columnExist.contains(i)) continue;
            // 0,0  1,1  2,2 都是正斜线上的点  行列差
            if(forwardSlashExist.contains(row - i)) continue;
            // 2,0  1,1  0,2 都是反斜线上的点  行列和
            if(backSlashExist.contains(row + i)) continue;
            columnExist.add(i);
            forwardSlashExist.add(row - i);
            backSlashExist.add(row + i);
            // 继续到下一行中进行列遍历
            backtrack(row + 1 , n, columnExist, forwardSlashExist, backSlashExist);
            // 退出的时候清理  下次循环该行列斜线都没有被占  不应还是存在 会造成干扰
            columnExist.remove(i);
            forwardSlashExist.remove(row - i);
            backSlashExist.remove(row + i);
        }

    }


    public int bitBacktrack(int row , int n, int columnBit, int forwardSlashBit, int backSlashBit) {
        if( row == n ) return 1;
        int count = 0;
        int availablePos = (1<<n -1 ) & (~(columnBit | forwardSlashBit| backSlashBit));
        while(availablePos != 0 ) {
            // 找到最低为1位
            int pos = availablePos  & (-availablePos);
            // 最低为1位设置为0
            availablePos = availablePos & (availablePos - 1);
            // 列位不变 正对角线修改对应位为1 后右移一位  反对角线修改对应值为1后左移一位
            count += bitBacktrack(row+ 1, n, columnBit| pos, (forwardSlashBit | pos) << 1, (backSlashBit | pos) >> 1);
        }
        return count;
    }


}
